package class05

/*
	LRU内存替换算法的实现，假设空间仅支持K个key，结构体需要自行判单对key的保留与替换，
	要求：get put 方法的事件复杂度为O（n）
	实现：
		哈希表 + 双向链表
		哈希表记录key与之对应的node，
		put 时直接记录节点，并将节点的数据接到链表结尾
		get时，需要找到key对应的node，通过node找到前一个与后一个节点，并且将前后节点连接，自己放到链表尾部
*/
type LRUNode struct {
	Key   string
	Value int
	Next  *LRUNode
	Last  *LRUNode
}

type MyDoubleList struct {
	Head *LRUNode
	Tail *LRUNode
}

func (md *MyDoubleList) AddNode(node *LRUNode) {
	if node == nil {
		return
	}
	if md.Head == nil {
		md.Head, md.Tail = node, node
	} else {
		md.Tail.Next = node
		node.Last = md.Tail
		md.Tail = node
	}
}

func (md *MyDoubleList) ChangeNodeToTail(node *LRUNode) {
	if node == nil {
		return
	}
	if node == md.Tail {
		return
	}
	if node == md.Head { // 等于头时
		// 这块逻辑处理逻辑保持一致，方便后续代码复用
		md.Head = node.Next
		md.Head.Last = nil
	} else { // 位于中间时
		node.Last.Next = node.Next
		node.Next.Last = node.Last
	}
	md.Tail.Next = node
	node.Last = md.Tail
	node.Next = nil
	md.Tail = node
}

func (md *MyDoubleList) RemoveHead() *LRUNode {
	if md.Head == nil {
		return nil
	}
	res := md.Head
	if md.Head == md.Tail {
		md.Head = nil
		md.Tail = nil
	} else {
		md.Head = res.Next
		res.Next = nil
		md.Head.Last = nil
	}
	return res
}

func NewMyCache(capacity int) MyCache {
	return MyCache{
		nodeMap: make(map[string]*LRUNode),
		doubleList: MyDoubleList{},
		capacity: capacity,
	}
}

type MyCache struct {
	doubleList MyDoubleList
	nodeMap    map[string]*LRUNode
	capacity   int
}

func (mc *MyCache) Get(key string) interface{} {
	if n, ok := mc.nodeMap[key]; ok {
		mc.doubleList.ChangeNodeToTail(n)
		return n.Value
	} else {
		return nil
	}
}

func (mc *MyCache) Set(key string, value int) {
	if n, ok := mc.nodeMap[key]; ok {
		n.Value = value
		mc.doubleList.ChangeNodeToTail(n)
	} else {
		if len(mc.nodeMap) == mc.capacity {
			mc.RemoveMostUnusedCache()
		}
		n := &LRUNode{Value: value, Key: key}
		mc.doubleList.AddNode(n)
		mc.nodeMap[key] = n
	}
}

func (mc *MyCache) RemoveMostUnusedCache(){
	delete(mc.nodeMap, mc.doubleList.RemoveHead().Key)
}